home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / ghostscript / src / ialloc.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  13KB  |  413 lines
  1. /* Copyright (C) 1989, 1992, 1993 Aladdin Enterprises.  All rights reserved.
  2.  
  3. This file is part of Ghostscript.
  4.  
  5. Ghostscript is distributed in the hope that it will be useful, but
  6. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  7. to anyone for the consequences of using it or for whether it serves any
  8. particular purpose or works at all, unless he says so in writing.  Refer
  9. to the Ghostscript General Public License for full details.
  10.  
  11. Everyone is granted permission to copy, modify and redistribute
  12. Ghostscript, but only under the conditions described in the Ghostscript
  13. General Public License.  A copy of this license is supposed to have been
  14. given to you along with Ghostscript so you can know your rights and
  15. responsibilities.  It should be in a file named COPYING.  Among other
  16. things, the copyright notice and this notice must be preserved on all
  17. copies.  */
  18.  
  19. /* ialloc.c */
  20. /* Memory allocator for Ghostscript interpreter */
  21. #include "gx.h"
  22. #include "memory_.h"
  23. #include "alloc.h"
  24. #include "astate.h"
  25. #include "ivmspace.h"
  26.  
  27. /* Import the debugging variables from gsmisc.c. */
  28. extern int gs_alloc_debug;
  29. extern byte gs_alloc_fill_alloc;
  30. extern byte gs_alloc_fill_free;
  31.  
  32. /* Forward references */
  33. private int alloc_add_chunk(P2(alloc_state_ptr, uint));
  34. private char *alloc_large(P3(alloc_state_ptr, uint, const char *));
  35. private void alloc_free_large(P3(char *, uint, const char *));
  36.  
  37. /* A public memory_procs for this allocator. */
  38. const gs_memory_procs alloc_memory_procs = {
  39.     alloc,
  40.     alloc_free
  41. };
  42.  
  43. /* The only allocator instance (for now). */
  44. private alloc_state as_current;
  45. alloc_state_ptr alloc_state_current = &as_current;
  46.  
  47. /* Debugging printout */
  48. #ifdef DEBUG
  49. #  define alloc_print_block(rtag, tag, blk, sz)\
  50.     fprintf(gs_debug_out, "[a:%c:%c:%s] %lx(%u)\n", rtag, tag,\
  51.         client_name, (ulong)blk, sz)
  52. #  define alloc_print(rtag, tag, blk, sz)\
  53.     if ( gs_debug['A'] || (gs_debug['a'] && align_round(sz) > max_chain_size) )\
  54.       alloc_print_block(rtag, tag, blk, sz)
  55. #  define alloc_print_large(rtag, tag, blk, sz)\
  56.     if ( gs_debug['A'] | gs_debug['a'] )\
  57.       alloc_print_block(rtag, tag, blk, sz)
  58. #else
  59. #  define alloc_print(rtag, tag, blk, sz)
  60. #  define alloc_print_large(rtag, tag, blk, sz)
  61. #endif
  62.  
  63. /* ------ Initialize/status ------ */
  64.  
  65. /* Initialize the allocator */
  66. void
  67. alloc_init(const gs_memory_procs *mprocs, uint chunk_size)
  68. {    register alloc_state_ptr ap = alloc_state_current;
  69.     memset(ap, 0, sizeof(alloc_state));    /* do it all at once */
  70.     ap->chunk_size = chunk_size;
  71.     ap->big_size = chunk_size / 4;
  72.     ap->mprocs = mprocs;
  73.     ap->last_freed = 0;
  74.        {    extern void alloc_save_init(P0());
  75.         alloc_save_init();
  76.        }
  77. }
  78.  
  79. /* Return the global/local attribute of the allocator. */
  80. uint
  81. alloc_current_local(void)
  82. {    alloc_state_ptr ap = alloc_state_current;
  83.     return ap->local_attr;
  84. }
  85.  
  86. /* Select the current local or global allocator. */
  87. /* Return the previous state. */
  88. /****** BOGUS ******/
  89. uint
  90. alloc_select_local(uint local)
  91. {    alloc_state_ptr ap = alloc_state_current;
  92.     uint prev_local = ap->local_attr;
  93.     ap->local_attr = local;
  94.     return prev_local;
  95. }
  96.  
  97. /* Return the status of the allocator: space used, total space. */
  98. void
  99. alloc_status(long *pused, long *ptotal)
  100. {    register alloc_state_ptr ap = alloc_state_current;
  101.     *pused = (ap->cbot - ap->cbase) + (ap->climit - ap->ctop) + ap->used;
  102.     *ptotal = ap->total;
  103. }
  104.  
  105. /* ------ Allocation and freeing ------ */
  106.  
  107. /* Allocate an object.  Return 0 if not enough room. */
  108. char *
  109. alloc(uint num_elts, uint elt_size, const char *client_name)
  110. {    register alloc_state_ptr ap = alloc_state_current;
  111.     uint size = num_elts * elt_size;
  112.     uint block_size;
  113.     uint left;
  114.     if ( size >= ap->big_size )
  115.        {    /* Large object, do a separate malloc. */
  116.         char *block = alloc_large(ap, size, client_name);
  117.         if ( block != NULL ) return block;
  118.         if ( size > ap->chunk_size )
  119.             return 0;    /* can't alloc */
  120.        }
  121.     block_size = align_round(size);
  122.     if ( block_size <= max_chain_size )
  123.        {    /* See if we can use a freed block. */
  124.         char **fptr = &ap->free[block_size >> log2_align_mod];
  125.         char *block = *fptr;
  126.         if ( block != 0 )
  127.            {    *fptr = *(char **)block;
  128.             alloc_print('+', '#', block, size);
  129.             if ( gs_alloc_debug )
  130.               memset(block, gs_alloc_fill_alloc, block_size);
  131.             return block;
  132.            }
  133.        }
  134.     left = ap->ctop - ap->cbot;
  135.     if ( block_size > left )
  136.        {    uint csize = ap->chunk_size;
  137.         while ( !alloc_add_chunk(ap, csize) )
  138.            {    alloc_print('+', '?', (ulong)0, size);
  139.             /* Things are desperate, but perhaps not hopeless. */
  140.             if ( (csize >>= 1) < block_size )
  141.                 return 0;    /* no hope */
  142.            }
  143.        }
  144.     if ( elt_size == 1 )
  145.        {    /* Unaligned block */
  146.         ap->ctop -= size;
  147.         alloc_print('+', '>', ap->ctop, size);
  148.         if ( gs_alloc_debug )
  149.             memset(ap->ctop, gs_alloc_fill_alloc, size);
  150.         return (char *)ap->ctop;
  151.        }
  152.     else
  153.        {    /* Aligned block */
  154.         char *block = (char *)ap->cbot;
  155.         ap->cbot += block_size;
  156.         alloc_print('+', '<', block, size);
  157.         if ( gs_alloc_debug )
  158.             memset(block, gs_alloc_fill_alloc, block_size);
  159.         return block;
  160.        }
  161. }
  162.  
  163. /* Free an object, if possible. */
  164. /* Note that if a save is in effect, objects in chunks older than */
  165. /* the save, and objects allocated with malloc before the save, */
  166. /* must not be freed. */
  167. void
  168. alloc_free(char *cobj, uint num_elts, uint elt_size, const char *client_name)
  169. {    register alloc_state_ptr ap = alloc_state_current;
  170.     uint size = num_elts * elt_size;
  171.     uint block_size;
  172.     if ( size >= ap->big_size )
  173.     {    /* Object was allocated with malloc. */
  174.         alloc_free_large(cobj, size, client_name);
  175.         return;
  176.     }
  177.     if ( gs_alloc_debug )
  178.         memset(cobj, gs_alloc_fill_free, size);
  179. #define obj ((byte *)cobj)
  180.     if ( obj == ap->ctop )
  181.        {    /* Don't free the object if we're in a save and */
  182.         /* this object wasn't allocated since the save. */
  183.         if ( ap->current.save_level == ap->save_level ||
  184.              /* We know the current chunk is the same as */
  185.              /* the one in as->saved->state */
  186.              obj < ap->saved_ctop
  187.            )
  188.             ap->ctop += size;
  189.         alloc_print('-', '>', obj, size);
  190.         return;
  191.        }
  192.     else if ( obj + (block_size = align_round(size)) == ap->cbot )
  193.        {    /* Freeing an aligned object.  Same check. */
  194.         if ( ap->current.save_level == ap->save_level ||
  195.              obj >= ap->saved_cbot
  196.            )
  197.             ap->cbot = obj;
  198.         alloc_print('-', '<', obj, size);
  199.         return;
  200.        }
  201.     else if ( !ptr_is_in_chunk(obj, &ap->current) )
  202.        {    /* In another chunk, check its save level. */
  203.         /* We rely on the chunk list being ordered */
  204.         /* by decreasing save level. */
  205.         int level = ap->save_level;
  206.         alloc_chunk *cp = ap->last_freed;
  207.         if ( cp != 0 && ptr_is_in_chunk(obj, cp) )  /* cache hit */
  208.          { if ptr_lt(obj, cp->bot) goto pxf;
  209.            else goto pnf;
  210.          }
  211.         for ( cp = ap->current.next; cp != 0; cp = cp->next )
  212.          { if ( cp->save_level == level )
  213.              { if ( ptr_is_in_chunk(obj, cp) )
  214.              { if ( ptr_lt(obj, cp->bot) ) goto pbf;
  215.                /* Unaligned, not freeable. */
  216.                alloc_print('-', '~', obj, size);
  217.                goto pnf;
  218.              }
  219.              }
  220.            else
  221.              { /* This is the chunk that straddles the save. */
  222.                /* Check whether the object being freed */
  223.                /* was allocated since the save. */
  224.                if ( ptr_between(obj, ap->saved_cbot, cp->bot) )
  225.              goto pxf;
  226.                goto pnf;
  227.              }
  228.          }
  229. pnf:        /* Older save level, not freeable. */
  230.         alloc_print('-', '\\', obj, size);
  231.         return;
  232. pbf:        /* If we get here, OK to put the block on a free list. */
  233.         ap->last_freed = cp;
  234. pxf:        ;
  235.        }
  236.     else if ( obj >= ap->cbot )    /* not aligned object, punt */
  237.        {    alloc_print('-', '~', obj, size);
  238.         return;
  239.        }
  240.     else if ( ap->current.save_level < ap->save_level &&
  241.           obj < ap->saved_cbot
  242.         )
  243.     {    /* Current chunk straddles the current save, and */
  244.         /* object is older than the current save. */
  245.         /* (Same check as above.) */
  246.         alloc_print('-', '!', obj, size);
  247.         return;
  248.     }
  249.     /* Put on a free list if small enough */
  250.     alloc_print('-', '#', obj, size);
  251.     if ( block_size <= max_chain_size && block_size >= sizeof(char **) )
  252.        {    char **fptr = &ap->free[block_size >> log2_align_mod];
  253.         *(char **)cobj = *fptr;
  254.         *fptr = cobj;
  255.        }
  256. #undef obj
  257. }
  258.  
  259. /* Grow an object.  This may require allocating a new copy. */
  260. /* Return 0 if not enough room. */
  261. /****** Note: the object must have been allocated at
  262.  ****** the current save level. */
  263. byte *
  264. alloc_grow(byte *obj, uint old_num, uint new_num, uint elt_size,
  265.   const char *client_name)
  266. {    register alloc_state_ptr ap = alloc_state_current;
  267.     uint old_size = old_num * elt_size;
  268.     uint new_size = new_num * elt_size;
  269.     byte *nobj;
  270.     if ( new_size == old_size ) return obj;
  271.     if ( new_size < ap->big_size ) /* try to grow in place */
  272.       { uint old_block_size;
  273.         uint new_block_size;
  274.         if ( obj == ap->ctop )
  275.           { /* Might be able to grow in place */
  276.         uint diff = new_size - old_size;
  277.         if ( diff <= ap->ctop - ap->cbot )
  278.           { alloc_print('>', '>', obj, new_size);
  279.             ap->ctop -= diff;
  280.             memcpy(ap->ctop, obj, old_size);
  281.             return ap->ctop;
  282.           }
  283.           }
  284.         old_block_size = align_round(old_size);
  285.         new_block_size = align_round(new_size);
  286.         if ( obj + old_block_size == ap->cbot )
  287.           { /* Might be able to grow in place */
  288.         uint diff = new_block_size - old_block_size;
  289.         if ( diff <= ap->ctop - ap->cbot )
  290.           { alloc_print('>', '<', obj, new_size);
  291.             ap->cbot += diff;
  292.             return obj;
  293.           }
  294.           }
  295.       }
  296.     /* Can't grow in place.  Allocate a new object and copy. */
  297.     nobj = (byte *)alloc(new_num, elt_size, client_name);
  298.     if ( nobj == 0 )
  299.         return 0;
  300.     memcpy(nobj, obj, old_size);
  301.     alloc_free((char *)obj, old_num, elt_size, client_name);
  302.     alloc_print('>', '&', obj, new_size);
  303.     return nobj;
  304. }
  305.  
  306. /* Shrink an object. */
  307. /****** Note: the object must have been allocated at
  308.  ****** the current save level. */
  309. byte *
  310. alloc_shrink(byte *obj, uint old_num, uint new_num, uint elt_size,
  311.   const char *client_name)
  312. {    register alloc_state_ptr ap = alloc_state_current;
  313.     uint old_size = old_num * elt_size;
  314.     uint new_size = new_num * elt_size;
  315.     if ( new_size == old_size ) return obj;
  316.     if ( old_size >= ap->big_size )
  317.       { /* Allocate a new block. */
  318.         byte *nobj = (byte *)alloc(new_num, elt_size, client_name);
  319.         if ( nobj == 0 ) return obj; /* can't shrink, leave as is */
  320.         memcpy(nobj, obj, new_size);
  321.         alloc_free((char *)obj, old_num, elt_size, client_name);
  322.         alloc_print('<', '&', obj, new_size);
  323.         return nobj;
  324.       }
  325.     else if ( obj == ap->ctop )
  326.       { /* Move the object up in place. */
  327.         /* memcpy doesn't do this properly. */
  328.         register byte *from = obj + new_size;
  329.         register byte *to = obj + old_size;
  330.         while ( from > obj ) *--to = *--from;
  331.         obj = ap->ctop = to;
  332.       }
  333.     else
  334.       { uint new_block_size = align_round(new_size);
  335.         alloc_free((char *)(obj + new_block_size),
  336.                1, align_round(old_size) - new_block_size,
  337.                "alloc_shrink");
  338.       }
  339.     alloc_print('<', ' ', obj, new_size);
  340.     return obj;
  341. }
  342.  
  343. /* ------ Private routines ------ */
  344.  
  345. /* Allocate (with malloc) an object too large to be put in a chunk. */
  346. /* Return NULL on failure. */
  347. private char *
  348. alloc_large(alloc_state_ptr ap, uint size, const char *client_name)
  349. {    alloc_block *mblock = (alloc_block *)
  350.       (*ap->mprocs->alloc)(1, alloc_block_size + size, client_name);
  351.     char *block;
  352.     if ( mblock == NULL ) return NULL;
  353.     block = (char *)mblock + alloc_block_size;
  354.        alloc_print_large('+', '*', block, size);
  355.     mblock->next = ap->malloc_chain;
  356.     mblock->size = size;
  357.     mblock->save_level = ap->save_level;
  358.     mblock->cap = ap;
  359.     ap->malloc_chain = mblock;
  360.     ap->used += size;
  361.     ap->total += size;
  362.     return block;
  363. }
  364.  
  365. /* Allocate a new chunk.  Return true if successful. */
  366. #define chunk_head_size align_round(sizeof(alloc_chunk))
  367. private int
  368. alloc_add_chunk(register alloc_state_ptr ap, uint csize)
  369. {    char *space =
  370.       (*ap->mprocs->alloc)(1, chunk_head_size + csize, "alloc chunk");
  371.     long discard;
  372.     if ( space == NULL )
  373.         return 0;
  374.     ap->num_chunks++;
  375.     /* Accumulate statistics */
  376.     ap->total += csize;
  377.     alloc_status(&ap->used, &discard);
  378.     /* Stash the state of the old chunk */
  379.     if ( ap->current_ptr != 0 )    /* check for very first chunk */
  380.         *ap->current_ptr = ap->current;
  381.     /* Initialize the new chunk */
  382.     ap->cbase = ap->cbot = (byte *)space + chunk_head_size;
  383.     ap->climit = ap->ctop = ap->cbot + csize;
  384.     ap->current.next = ap->current_ptr;
  385.     ap->current.save_level = ap->save_level;
  386.     ap->current_ptr = (alloc_chunk *)space;
  387.     return 1;
  388. }
  389. #undef chunk_head_size
  390.  
  391. /* Free a large object (allocated with malloc). */
  392. private void
  393. alloc_free_large(char *cobj, uint size, const char *client_name)
  394. {    alloc_block **prev;
  395.     alloc_block *mblock = (alloc_block *)(cobj - alloc_block_size);
  396.     alloc_state_ptr ap = mblock->cap;
  397.     if ( mblock->save_level == ap->save_level )
  398.      for ( prev = &ap->malloc_chain; *prev != 0; prev = &mblock->next )
  399.        {    mblock = *prev;
  400.         if ( (char *)mblock + alloc_block_size == cobj )
  401.            {    *prev = mblock->next;
  402.             ap->used -= size;
  403.             ap->total -= size;
  404.             (*ap->mprocs->free)((char *)mblock,
  405.                     1, size + alloc_block_size,
  406.                     "large object");
  407.             alloc_print_large('-', '*', cobj, size);
  408.             return;
  409.            }
  410.        }
  411.     alloc_print('-', '?', cobj, size);
  412. }
  413.